Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Longest Palindromic Substring

Problem Statement

Given a string s, return the longest palindromic substring in s.

A string is called palindromic if it reads same from forward as backward.

A substring is a contiguous sequence of characters in the string.

Examples

  • Example 1:

    • Input: s = "racecar"
    • Expected Output: "racecar"
    • Justification: The entire string is a palindrome and is the longest substring.
  • Example 2:

    • Input: s = "abccd"
    • Expected Output: "cc"
    • Justification: The longest palindromic substring is "cc" in the string abccd.
  • Example 3:

    • Input: s = "xyzzy"
    • Expected Output: "yzzy"
    • Justification: The substring "yzzy" is the longest palindromic substring.

Solution

To solve this problem, the Expand Around Center technique is an effective approach. The idea is to consider each character in the string as the center of a potential palindrome and expand in both directions to find the length of the palindrome. This technique is efficient because it utilizes the symmetry of palindromes and checks for both odd and even length palindromes by expanding around a center point or a center gap. This approach is most effective because it directly narrows down the search to potential palindromic centers, reducing unnecessary comparisons, and it can handle palindromes of both odd and even lengths without requiring additional data structures.

The key to this method is to iterate over the string, treating each character and each gap between characters as potential centers of palindromes. For each center, we expand outwards, comparing characters until they no longer match. We record the length of each palindrome found and update the maximum palindrome length accordingly. This process is repeated until all potential centers have been examined. The simplicity and directness of expanding around centers make this method both intuitive and efficient for finding the longest palindromic substring.

Step-by-Step Algorithm

  1. Check for Empty String: If the input string s is empty or null, return an empty string since there's no palindrome to find.

  2. Initialize Start and End Indices: Start and end indices (start and end) are initialized to track the boundaries of the longest palindromic substring found so far. Initially, both are set to 0.

  3. Iterate Through the String: Loop through each character in the string with index i. For each character, two types of palindrome checks are performed: one assuming the current character as the center of an odd-length palindrome and another assuming the current character and the next character as the center for an even-length palindrome.

  4. Expand Around Centers: For each character at index i:

    • Call expandAroundCenter(s, i, i) to check for the longest odd-length palindrome centered at i.
    • Call expandAroundCenter(s, i, i + 1) to check for the longest even-length palindrome centered between i and i + 1.
    • Compare the lengths of these two palindromes and keep the length of the longer one.
  5. Update Longest Palindrome Boundaries: If the palindrome found is longer than the current longest palindrome (end - start), update the start and end indices to the new boundaries of this palindrome.

  6. Return the Longest Palindromic Substring: Use the start and end indices to extract the longest palindromic substring from s and return it.

Helper Function expandAroundCenter()

  1. Initialize Pointers: This function receives the string s and two indices, left and right, which represent the center of the palindrome to be expanded.

  2. Expand the Palindrome: While left and right are within the bounds of the string and the characters at these indices are equal, decrement left and increment right. This expansion continues as long as the substring is a palindrome.

  3. Return Length: Once the expansion stops, return the length of the palindrome found by calculating right - left - 1. This subtraction accounts for the last increment and decrement that occurred when the while loop condition failed.

Algorithm Walkthrough

Let's consider the input: s = "xyzzy".

  1. Initialize Variables: start = 0, end = 0. These variables will keep track of the start and end indices of the longest palindromic substring found so far.

  2. Loop Through String Characters:

    • Iteration 1: i = 0
      • Inner Loop (Odd Length Palindrome):
        • len1 = expandAroundCenter("xyzzy", 0, 0). Since s.charAt(0) == s.charAt(0), the loop expands.
        • Once expanded, left = -1 and right = 1, so len1 = right - left - 1 = 1.
      • Inner Loop (Even Length Palindrome):
        • len2 = expandAroundCenter("xyzzy", 0, 1). Since s.charAt(0) != s.charAt(1), the loop breaks. len2 = 0.
      • Comparison:
        • len = max(1, 0) = 1. Since len > end - start, update start = 0, end = 0.
    • Iteration 2: i = 1
      • Inner Loop (Odd Length Palindrome):
        • len1 = expandAroundCenter("xyzzy", 1, 1). Since s.charAt(1) == s.charAt(1), the loop expands.
        • Once expanded, left = 0 and right = 2, so len1 = right - left - 1 = 1.
      • Inner Loop (Even Length Palindrome):
        • len2 = expandAroundCenter("xyzzy", 1, 2). Since s.charAt(1) != s.charAt(2), the loop breaks. len2 = 0.
      • Comparison:
        • len = max(1, 0) = 1. Since len > end - start, no update.
    • Iteration 3: i = 2
      • Inner Loop (Odd Length Palindrome):
        • len1 = expandAroundCenter("xyzzy", 2, 2). Since s.charAt(2) == s.charAt(2), the loop expands.
        • Once expanded, left = 1 and right = 3, so len1 = right - left - 1 = 1.
      • Inner Loop (Even Length Palindrome):
        • len2 = expandAroundCenter("xyzzy", 2, 3). Since s.charAt(2) == s.charAt(3), the loop expands.
        • Since s.charAt(1) == s.charAt(4), the loop expands
        • Once expanded, left = 0 and right = 5, so len2 = right - left - 1 = 4.
      • Comparison:
        • len = max(1, 4) = 4. Since len > end - start, update start = 1, end = 4.
    • Iteration 4: i = 3
      • Inner Loop (Odd Length Palindrome):
        • len1 = expandAroundCenter("xyzzy", 3, 3). Since s.charAt(3) == s.charAt(3), the loop expands.
        • Once expanded, left = 2 and right = 4, so len1 = right - left - 1 = 1.
      • Inner Loop (Even Length Palindrome):
        • len2 = expandAroundCenter("xyzzy", 3, 4). Since s.charAt(3) != s.charAt(4), the loop doesn't expand.
      • Comparison:
        • len = max(1, 0) = 1. Since len < end - start, no update.
    • Iteration 5: i = 4
      • Inner Loop (Odd Length Palindrome):
        • len1 = expandAroundCenter("xyzzy", 4, 4). Since s.charAt(4) == s.charAt(4), the loop expands.
        • Once expanded, left = 3 and right = 5, so len1 = right - left - 1 = 1.
      • Inner Loop (Even Length Palindrome):
        • len2 = expandAroundCenter("xyzzy", 4, 5). Since the index is out of bounds, the loop doesn't expand.
      • Comparison:
        • len = max(1, 0) = 1. Since len < end - start, no update.
  3. Return Result: The longest palindromic substring is "yzzy".

Code

Java

. . . .

Complexity Analysis

Time Complexity

  • : The main factor contributing to the time complexity is the need to expand around each character (and each pair of characters for even-length palindromes) to check for palindromic substrings. For each of the n characters, the expansion in the worst case can go up to n characters (if the entire string from that point is a palindrome). Therefore, the time complexity is quadratic, .

Space Complexity

  • : The space complexity is constant because the space used does not scale with the input size.
Longest Palindromic Substring (medium)
Single Element in a Sorted Array (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity